package Offer.offer2017;

import domain.ListNode;

/**
 * 单链表的第一个公共节点
 * Created by 雷文康 on 2018/1/4.
 */
public class Test37 {
     public static ListNode findFirstCommonNode(ListNode head1, ListNode head2){
         if (head1 == null || head2 == null){
             return null;
         }
         ListNode p1 = head1;
         int length1 = 0;
         while (p1 != null){
             length1++;
             p1 = p1.next;
         }

         ListNode p2 = head2;
         int length2 = 0;
         while (p2 != null){
             length2++;
             p2 = p2.next;
         }
         int k = length1 - length2;
         ListNode pLong = head1;
         ListNode pShort = head2;
         if (k < 0){
             k = -k;
             pLong = head2;
             pShort = head1;
         }
         for (int i = 1; i <= k; i++) {
             pLong = pLong.next;
         }
         while (pLong != null && pShort != null && pLong != pShort) {
             pLong = pLong.next;
             pShort = pShort.next;
         }
         return pLong;
     }
}
